/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    let settled = []
    let ans = []
    const dfs = (x, y) => {
        for (let i = 0; i < settled.length; i++) {
            if (settled[i][1] == y || (Math.abs(x - settled[i][0]) === Math.abs(y - settled[i][1]))) return
        }
        settled.push([x, y])
        if (x === n - 1) {
            ans.push([...settled])
        }
        let j = 0;
        while (j < n) {
            dfs(x + 1, j)
            j++
        }
        settled.pop()
    }
    for(let j = 0; j < n; j++) {
        dfs(0, j)
    }
    let res = []
    for(let i = 0; i < ans.length; i++) {
        let sarr = []
        for(let j = 0; j < n; j++) {
            let s= ''
            for(let k = 0; k < n; k++) {
                if(ans[i][j][1] !== k) {
                    s += '.'
                } else {
                    s += 'Q'
                }
            }
            sarr.push(s)
        }
        res.push(sarr)
    }
    return res
};